#include <algorithm>
#include <bitset>
#include <string>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include "Permutation.h"

using std::string;
using std::bitset;


//this is for disabling a visual studio warning about a potentialy 
//unsafe use of funcation std::copy
#pragma warning(disable:4996)

//--------------------------------------------------------------------------
// Operator==: Related permutations are equal if their indexes are the same
//--------------------------------------------------------------------------
bool RelatedPermutation::operator==(const RelatedPermutation &other) const
{
	if (this==&other)
	{
		return true;
	}	

	return (this->GetIndex())==(other.GetIndex());
}

//--------------------------------------------------------------------------
// Operator!=: Related permutations are equal if their indexes are the same
//--------------------------------------------------------------------------
bool RelatedPermutation::operator!=(const RelatedPermutation &other) const
{
	return !((*this)==other);
}
//--------------------------------------------------------------------------

//--------------------------------------------------------------------------
// Permutation
// A class to save a list of binary words
//--------------------------------------------------------------------------

//--------------------------------------------------------------------------
// Public functions 
//--------------------------------------------------------------------------

//--------------------------------------------------------------------------
// Ctors
//--------------------------------------------------------------------------

Permutation::Permutation(VERTEX_SIZE *permutationList,int wordLen, int groupSize, int name)
: m_WordLen(wordLen), m_GroupSize(groupSize), m_Permutation(permutationList), m_GroupIndex(name)
{}

Permutation::Permutation(VERTEX_SIZE *permutationList,int wordLen = 1, int groupSize = 1)
: m_WordLen(wordLen), m_GroupSize(groupSize), m_Permutation(permutationList), m_GroupIndex(Permutation::NO_INDEX)
{}

//--------------------------------------------------------------------------
// dtor
//--------------------------------------------------------------------------

Permutation::~Permutation(void)
{}


//--------------------------------------------------------------------------
// CountIntersection : Receives  int arrays and counts how many elements are 
//								 in the intersection between it and the 
//								 current perm
// Parameters:
// groupB - permutation as unsigned longs
// groupBrows - how many rows are in groupB
//--------------------------------------------------------------------------
int Permutation::CountIntersection(VERTEX_SIZE* groupB, int groupBrows)
{
	int intersectionSize = 0;

	for (int i=0; i<m_GroupSize; i++)
	{	
		for (int j=0; j<groupBrows; j++)
		{
			if (m_Permutation[i]==groupB[j])
			{	
				intersectionSize++;
			}
		}
	}
	return intersectionSize;
}

//--------------------------------------------------------------------------
// GetMatrixColumns: Returns a new matrix which is this matrix transposed
//--------------------------------------------------------------------------
vector<bool>* Permutation::GetMatrixColumns() const
{
	return TransposeMatrixBits(m_GroupSize,m_WordLen);
}

//--------------------------------------------------------------------------
// GetMatrixRows: Returns this matrix
//--------------------------------------------------------------------------
VERTEX_SIZE* Permutation::GetMatrixRows() const
{
	return m_Permutation;
}

//--------------------------------------------------------------------------
// UpdateMatrix: Updates permutation matrix
// Parameters:
// newPerm - new matrix (list of binary words - rows)
// newGroupSize - how many rows in new matrix
//--------------------------------------------------------------------------
void Permutation::UpdateMatrix(VERTEX_SIZE* newPerm, int newGroupSize)
{
	if (newPerm == NULL && newGroupSize != 0)
	{
		// Do not save a null matrix
		Debug::PrintDebugMsg("Trying to update matrix to NULL, not saving updated matrix");
		return;
	}
	m_GroupSize = newGroupSize;
	m_Permutation = newPerm;
}

//--------------------------------------------------------------------------
// GetGroupSize: Returns group size
//--------------------------------------------------------------------------
int Permutation::GetGroupSize() const
{
	return m_GroupSize;
}

//--------------------------------------------------------------------------
// GetMatrixWithoutIntersection : Removes the intersection between 2 matrices
//                                from one and returns the clean matrix
// Parameters:
// matrixToClean - matrix to remove intersection from
// matrixToCleanRows - how many rows in matrixToClean
// otherMatrix - matrix to check intersection with
// otherMatrixRows - how many rows in otherMatrix
// intersectionSize - how many intersecting rows both matrices have
// Returns: pointer to new binary word array without intersection
//--------------------------------------------------------------------------
 VERTEX_SIZE* Permutation::GetMatrixWithoutIntersection(VERTEX_SIZE* matrixToClean, int matrixToCleanRows, VERTEX_SIZE* otherMatrix,
	 int otherMatrixRows, 
	 int intersectionSize)
{
	// If permutations are the same, nothing to do
	if (intersectionSize == 0)
	{
		return matrixToClean;
	}

	// If we are cleaning the whole matrix, return NULL
	if (matrixToCleanRows == intersectionSize)
	{
		return NULL;
	}

	VERTEX_SIZE* resultMatrix;
	try
	{
		 resultMatrix = new VERTEX_SIZE[matrixToCleanRows - intersectionSize];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed while allocating matrix without intersection");
		return NULL;
	}


	int copiedRows = 0;

	for (int i=0; i < matrixToCleanRows; i++)
	{
		bool copyRow = true;
		int j=0;
		while (j< otherMatrixRows && copyRow)
		{
			if (otherMatrix[j] == matrixToClean[i])
			{
				copyRow = false;
			}
			j++;
		}
		if (copyRow)
		{
			resultMatrix[copiedRows] = matrixToClean[i];
			copiedRows++;
		}
	}
	
	return resultMatrix;
}

//--------------------------------------------------------------------------
// NextPermutation 
// Returns a new permutation object with the next permutation on columns.
// the next permutation is a random permutations of the columns
// on the current (this) permutation object.
// this function allocates memory for the new permutation object that is created.
// it is the responsibility of the caller to free this memory.
//
// Returns: Permutation*
// a pointer to the new permutation object that is created.
//--------------------------------------------------------------------------
Permutation *Permutation::NextPermutation()
{
	int columnCount = m_WordLen;
	int rowCount = m_GroupSize;

	vector<bool> *newColumnsPermutation = NULL;
	try
	{
		newColumnsPermutation = new vector<bool>[columnCount];	
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Logger::LogMessage("memory allocation failed while allocating in NextPermutation");
		return NULL;
	}

	//get a copy of the columns array and work on the copy:
	vector<bool> *matrixColumns = GetMatrixColumns();
	if(matrixColumns == NULL)
	{
		Debug::PrintDebugMsg("Could not get matrix columns, not calculating next permutation");
		delete[] newColumnsPermutation;
		return NULL;
	}

	for(int i=0; i < columnCount; i++)
	{
		//randomly choose an index
		int randIndex = rand() % (columnCount - i);
		//copy the vector in the chosen index to it's location in the new permutation
		for(int j = 0; j < rowCount; j++)
		{
			newColumnsPermutation[i].push_back(matrixColumns[randIndex][j]);
		}
		//remove the chosen value from the array and reduce its size
		for(int j = randIndex; j < columnCount-i-1; j++)
		{
			//copy the vector to a new cell in the permutation array.
			for (int k = 0; k < rowCount; k++)
			{
				matrixColumns[j][k] = matrixColumns[j+1][k];
			}			
		}
		matrixColumns[columnCount-i-1] = vector<bool>(); //invalidate the empty cell that was created
	}

	//no need for this any more:
	delete[] matrixColumns;

	// transpose the result to return to the original matrix
	VERTEX_SIZE *newMatrixRows = Permutation::TransposeColumnMatrixBit(newColumnsPermutation, m_WordLen,m_GroupSize);
	if (newMatrixRows == NULL)
	{
		Debug::PrintDebugMsg("Could not get matrix coulmns, not cacluating next permutation");
		delete[] newColumnsPermutation;
		return NULL;
	}

	//no need for this any more
	delete[] newColumnsPermutation;
	
	Permutation* returnPermutation;
	try
	{
		returnPermutation = new Permutation(newMatrixRows, columnCount, rowCount);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed while allocating for next");
		delete[] newMatrixRows;
		return NULL;
	}

	return returnPermutation;
}

 //--------------------------------------------------------------------------
 // operator== : Permutations are equal if their rows are equal
 //--------------------------------------------------------------------------
 bool Permutation::operator== (const Permutation &other) const
 {
	 if (this == &other)
	 {	
		return true;
	 }

	 if (m_GroupIndex != Permutation::NO_INDEX && m_GroupIndex == other.GetName())
	 {
		return true;
	 }

	if (m_GroupSize != other.GetGroupSize())
	{
		return false;
	}

	for (int i=0; i<m_GroupSize; i++)
	{
		int j=0;
		bool found = false;
		while (j< m_GroupSize && !found)
		{
			if (m_Permutation[i] == (other.GetMatrixRows()[j]))
			{
				found = true;
			}
			else 
			{
				j++;
			}
		}
		// if we went over all the other array and still didn't find
		// this item - they're not equal
		if (!found)
		{
			return false;
		}
	}

	return true;
 }

 //--------------------------------------------------------------------------
 // operator!= : Permutations are equal if their rows are equal
 //--------------------------------------------------------------------------
 bool Permutation::operator!= (const Permutation &other) const
 {
	return !(*this==other);
 }

 //--------------------------------------------------------------------------
 // AddRelatedPerm: Add a permutation to the list of related permutations
 // for this permutation
 // Parameters:
 // other - permutation to link to this one
 //--------------------------------------------------------------------------
 void Permutation::AddRelatedPerm(RelatedPermutation other)
 {
	 vector<RelatedPermutation>::iterator it = m_RelatedPerms.begin();
	 while (it < m_RelatedPerms.end() && (*it).GetGroupSize() > other.GetGroupSize())
	 {
		 it++;
	 }
	 m_RelatedPerms.insert(it,other);
 }

 //--------------------------------------------------------------------------
 // Clone:  Returns a new Permutation object - a copy of the original matrix 
 //         (without related permutations)
 //--------------------------------------------------------------------------
 Permutation* Permutation::Clone() const
 {
	int matrixSize = sizeof(VERTEX_SIZE)*m_GroupSize; // how many bytes to copy
	VERTEX_SIZE* matrixCopy;
	try
	{
		matrixCopy = new VERTEX_SIZE[m_GroupSize];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed while allocating matrix for clone");
		return NULL;
	}
	memcpy(matrixCopy,m_Permutation,matrixSize);
	Permutation* newPerm;
	try
	{
		newPerm = new Permutation(matrixCopy,m_WordLen,m_GroupSize,m_GroupIndex);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating permutation object in clone");
		return NULL;
	}
	newPerm->m_RelatedPerms = m_RelatedPerms;
	return newPerm;
 }

//--------------------------------------------------------------------------
//GetAllVertexNames
// Returns an array of all binary words in this permutation
//--------------------------------------------------------------------------
vector<bool>** Permutation::GetAllVertexNames()
{
	vector<bool> **verticesName;
	try
	{
		verticesName = new vector<bool>*[m_GroupSize];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while getting vertex names");
		return NULL;
	}

	for (int i=0; i<m_GroupSize; i++)
	{
		// Go over all words and save them in binary form
		vector<bool>* name = GetVertexNameBool(m_Permutation[i]); 
		if (name == NULL)
		{
			Debug::PrintDebugMsg("Cannot get vertex name, returning NULL for list");
			return NULL;
		}
		verticesName[i] = name;
	}
	return verticesName;
}

//--------------------------------------------------------------------------
// end Public
//--------------------------------------------------------------------------

//--------------------------------------------------------------------------
// Private functions 
//--------------------------------------------------------------------------

//--------------------------------------------------------------------------
// TransposeMatrixBits : Returns the matrix transposed
// Parameters:
// rowCount
// colCount
// Returns:
// New array with transposed bits
//--------------------------------------------------------------------------
vector<bool>* Permutation::TransposeMatrixBits(const int rowCount, const int colCount) const
{
	vector<bool> *transMatrix;
	try
	{
		transMatrix = new vector<bool>[colCount];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating matrix for transpose");
		return NULL;
	}

	// Go over each one of the numbers
	for (int i = 0; i < rowCount; i++)
	{
		// And set the bits from the right 
		VERTEX_SIZE currentNumber = m_Permutation[i];
		// and place its bits in the right places in the column array
		for (int j = colCount-1 ; j >= 0 ; j--)
		{
			int currentBit = currentNumber & 1; // Get last bit
			currentNumber = currentNumber >> 1; // Shift right to deal with next bit
			transMatrix[j].push_back(currentBit == 1); // Add next to start of vector
		}
	}
	return transMatrix;
}

//--------------------------------------------------------------------------
// TransposeColumnMatrixBit : Returns the matrix transposed
// Parameters:
// matrix
// rows
//		the size of the matrix array (wich is actualy the word length)
// cols
//		the number of elemnts in each cell of the matrix array
//		(wich is actualy the number of vetices in the group/permutaion)
// colCount
// Returns:
// New array with transposed bits
//--------------------------------------------------------------------------
VERTEX_SIZE* Permutation::TransposeColumnMatrixBit(vector<bool>* matrix, int rows, int cols)
{
	VERTEX_SIZE *transMatrix;
	try
	{
		transMatrix = new VERTEX_SIZE[cols];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating matrix for transpose");
		return NULL;
	}
	
	for (int i = 0; i < cols; i++)
	{
		bitset<sizeof(VERTEX_SIZE)*8> columnAsInt;

		for (int j = 0; j < rows; j++)
		{
			columnAsInt[j] = (matrix[rows-j-1])[i];
		}
		transMatrix[i] = columnAsInt.to_ulong();
	}

	return transMatrix;

}

//-------------------------------------------------------------------------
// GetStaticCopyVertexNameString - Returns string for vertex name in m_Wordlen bits
//-------------------------------------------------------------------------
vector<bool> *Permutation::GetVertexNameBool(VERTEX_SIZE vertex) const
{
	vector<bool> *vertexName;
	try
	{
		vertexName	= new vector<bool>();
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating vertex name");
		return NULL;
	}
	vector<bool>::iterator it = vertexName->begin();

	bitset <sizeof( VERTEX_SIZE ) * 8> bits( vertex );
	
	int i = 0;
	for(;i < m_WordLen; i++)
	{
		it = vertexName->insert(it, bits[i]);
	}
  
	return vertexName;
  
}

//-------------------------------------------------------------------------
// CleanPermutation: Removes duplicates from permutation and returns new
//                   size
// Parameters:
// perm - permutation to be cleaned
// size - current permutation size
// Returns:
// new size after duplicated rows were removed
//-------------------------------------------------------------------------
int Permutation::CleanPermutation(VERTEX_SIZE **permPointer, int size)
{
	int newSize = 0;
	vector<VERTEX_SIZE> rowsToCopy;
	VERTEX_SIZE *perm = *permPointer;

	for (int i = 0; i<size; i++)
	{
		bool found = false;
		for (int j=i+1; j<size && !found; j++)
		{
			if (perm[i] == perm[j])
			{
				found = true;
			}
		}
		// If not found - copy this row
		if (!found)
		{
			newSize++;
			rowsToCopy.push_back(perm[i]);
		}
	}

	vector<VERTEX_SIZE>::iterator start = rowsToCopy.begin();
	vector<VERTEX_SIZE>::iterator end = rowsToCopy.end();
	VERTEX_SIZE *newPerm;
	try
	{
		newPerm = new VERTEX_SIZE[newSize];
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while allocating matrix for clean matrix");
		perm = NULL;
		return 0;
	}


	// Copy the rows back to an array
	std::copy(start,end,newPerm);

	*permPointer = newPerm;

	return newSize;
}

//-------------------------------------------------------------------------
// Swap - Swaps 2 indexes in a vector
//-------------------------------------------------------------------------
void Permutation::Swap(std::vector<VERTEX_SIZE>& sourceVector, int index1, int index2)
{
	VERTEX_SIZE temp;

	temp = sourceVector[index1];
	sourceVector[index1] = sourceVector[index2];
	sourceVector[index2] = temp;
}
// end  Private
